#ifndef MISRAGRIESALGORITHM_H
#define MISRAGRIESALGORITHM_H

#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <string>
#include <map>
#include "../core/Sink.h"
#include "../core/OutputSink.h"
#include "../core/StringPiece.h"

using namespace std;

template<class T>
class MisraGriesAlgorithm : public Sink<T> {
    int m_capacity;
    map <T, int> storage;

public:
    MisraGriesAlgorithm(int capacity) {
        m_capacity = capacity;
    }

    void process(T r) {
        typename map<T, int>::iterator it = storage.find(r);

        if (it != storage.end()) {
            it->second = it->second + 1;
        } else {
            if ((signed int)storage.size() < m_capacity) {
                storage.insert(make_pair(r, 1));
            } else {
                for (map<StringPiece, int>::iterator it = storage.begin(); it != storage.end();) {
                    it->second--;
                    typename map<T, int>::iterator it_old = it;
                    it++;
                    if (it_old->second <= 0) {
                        storage.erase(it_old);
                    }
                }
            }
        }
    }

    void finish() {
        //OutputSink ss;
        stringstream ss;
        typename map<T,int>::iterator it;

        for (it = storage.begin(); it != storage.end(); ++it) {
            ss << (it->first).begin() << ' ';
        }
        return;
    }
};

#endif // MISRAGRIESALGORITHM_H
